AGC023 A Zero-Sum Ranges
まず問題文の条件を数式に変形する. ここで数列$ Aの累積和をとることを考える. $ S_0 = 0, S_i = S_{i - 1} + A_i($ i \geq 1)とすると数列$ Sは$ Aの累積和となる. すると問題は「$ S_r - S_{l - 1} = 0(1 \leq l \leq r)なる$ (l, r)の組は何通り考えられるか?」という問題に言い換えられる.
さらに数式を変形する. $ S_r - S_{l - 1} = 0は$ S_{l - 1}を右辺にもってくることで$ S_r = S_{l - 1}(l \leq r)となる. このように変形できれば, $ rを固定することで$ S_rと等しいような$ S_i(i < r)は何通り存在するかというのを数えればよくなる. これはmapなどの連想配列を用いることで高速に処理することができる(数列$ Aを座標圧縮してもよい). 計算量は$ O(N \log N)となる.